15. 三数之和

Similar Question

leading to the advanced question

611. 有效三角形的个数

Solution Tips

方案一: 暴力法

题目中要求找到所有「不重复」且和为 0 的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下，数组中的元素全部为 0，即 [0, 0, 0, 0, 0, ..., 0, 0, 0]

任意一个三元组的和都为 0。如果我们直接使用三重循环枚举三元组，会得到 O(N^3) 个满足题目要求的三元组（其中 N 是数组的长度）时间复杂度至少为 O(N^3 )。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此我们要换一种思路来考虑这个问题

var threeSum = function (nums) {
    const ret = [];
    nums.forEach((val, i) => {
        const target = 0 - val;
        const dup = [...nums];
        dup.splice(i, 1);
        dup.forEach((value, index) => {
            const another = target - value;
            const anotherIndex = dup.indexOf(another);
            if (anotherIndex !== -1 && anotherIndex !== index) {
                const newThree = [val, value, another];
                const exist = ret.find((val) => {
                    return newThree.sort().toString() === val.sort().toString();
                });
                if (!exist) {
                    ret.push(newThree);
                }
            }
        });
    });
    return ret;
};

方法二: 排序 + 跳过重复 + 对撞指针

nums.sort()
for first = 0 .. n-1
    // 只有和上一次枚举的元素不相同，我们才会进行枚举
    if first == 0 or nums[first] != nums[first-1] then
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                for third = second+1 .. n-1
                    if third == second+1 or nums[third] != nums[third-1] then
                        // 判断是否有 a+b+c==0
                        check(first, second, third)

var threeSum = function (nums) {
    const res = [];
    const len = nums.length;
    nums.sort((a, b) => a - b);

    // 优化1: 整个数组同符号，则无解
    if (nums[0] <= 0 && nums[len - 1] >= 0) {
        for (let i = 0; i < len - 2; i++) {
            // 优化2: 最左值为正数则一定无解
            if (nums[i] > 0) break;

            // 双指针
            let left = i + 1;
            let right = len - 1;
            // 指针对撞式结束循环
            while (left < right) {
                // 优化3: 最小和最大的同符号了, 不可能相加为 0
                if (nums[i] * nums[right] > 0) break;

                let sum = nums[i] + nums[left] + nums[right];
                if (sum === 0) {
                    res.push([nums[i], nums[left], nums[right]]);
                }

                if (sum <= 0) {
                    // left太小了，left指针右移
                    // 取等于，因为符合条件之后也需要移动指针
                    while (left < right && nums[left] === nums[++left]); // 如果相等就跳过
                }
                if (sum >= 0) {
                    // right太大了，right指针左移
                    while (left < right && nums[right] === nums[--right]); // 如果相等就跳过
                }
            }
            // 需要和上一次枚举的数不相同, 在这里跳过其实不太严谨, 可以参考四数之和
            if (nums[i] == nums[i - 1]) {
                continue;
            }
        }
    }
    return res;
};

优化的思路主要是基于 最小的数大于 0 , 或者 最小的数和最大的数同符号 (说明第二个数也是同符号), 等等必不可能为 0 的场景, 都直接跳过